В 1951 году Алан Тьюринг написал первую компьютерную программу, способную вести полную игру в шахматы [1521]. Но программа Тьюринга фактически никогда не эксплуатировалась на компьютере; она была испытана путем моделирования вручную в партии против очень слабого игрока-человека, который ее победил. Между тем, Д. Г. Принц [1238] написал и проверил на практике программу, которая решала шахматные задачи, но не могла вести полную игру. Первая программа, способная вести полную игру в стандартные шахматы, была написана Алексом Бернстейном [112], [113].

Джон Маккарти сформулировал идею альфа-бета-поиска в 1956 году, но не опубликовал свое открытие. В шахматной программе NSS [1128] используется упрощенная версия альфа-бета-поиска; она представляет собой первую шахматную программу, в которой было введено это усовершенствование. По данным Нильссона [1141], в программе игры в шашки Артура Самюэла [1349], [1350] также использовался альфа-бета-поиск, хотя Самюэл об этом не упоминал в опубликованных отчетах о своей системе. Статьи с описанием альфа-бета-поиска были опубликованы вначале 1960-х годов [198], [625], [1427]. Одна из реализаций полного альфа-бета-поиска описана Слаглем и Диксоном [1428] применительно к программе ведения игры калах. Кроме того, альфа-бета-поиск использовался в шахматной программе "Kotok-McCarthy", написанной студентом Джоном Маккарти [847]. Кнут и Мур [810] изложили историю создания алгоритма альфа-бета-поиска, а также привели доказательство его правильности и представили результаты анализа временной сложности. Проведенный ими анализ альфа-бета-поиска со случайным упорядочиванием преемников показал его асимптотическую сложность, что представляло собой довольно мрачный прогноз, поскольку соответствующий ему эффективный коэффициент ветвления b/logb не намного меньше, чем само значение Ь. После этого они отметили, что указанная асимптотическая формула является точной только для b>10 0 0 или таких порядков величин, тогда как часто упоминаемое значение относится к тому диапазону коэффициентов ветвления, который чаще всего встречается в настоящих играх. Перл [1187] показал, что альфа-бета-поиск является асимптотически оптимальным среди всех алгоритмов поиска в дереве игры на постоянную глубину.

В первом шахматном матче между компьютерами участвовала программа Kotok-McCarthy и программа "ITEP" (Institute of Theoretical and Experimental Physics), написанная в середине 1960-х годов в Московском институте теоретической и экспериментальной физики (ИТЕФ) [4]. Этот межконтинентальный матч проводился по телеграфу. Он закончился в 1967 году победой программы ITEP со счетом 3:1. Первой шахматной программой, которая успешно соревновалась с людьми, была программа МасНаск 6 [594]. Ее рейтинг, примерно равный 1400, был намного выше 1000 — уровня начинающего, но все же далеко не достигал рейтинга 2800 или больше, который требовался для выполнения предсказания Герберта Саймона, высказанного в 1957 году, что компьютерная программа станет чемпионом мира по шахматам через 10 лет [1419].